package com.bokee.archerwq.lab.algorithm;

import junit.framework.Assert;

import org.junit.Test;

public class BinarySearch {
	
	public int binarySearch(int[] a, int dest) {
		if (a == null) {
			return -1;
		}
		int length = a.length;
		int p = 0, q = length - 1;
		while (p <= q) {
			int r = (p + q) / 2;
			if (a[r] == dest) {
				return r;
			} else if (a[r] > dest) {
				q = r - 1;
			} else if (a[r] < dest) {
				p = r + 1;
			}
		}
		return -1;
	}

	@Test
	public void testBinarySearch() {
		int[] a = {2, 3, 5, 7, 9, 11, 13, 15, 17};
		Assert.assertEquals(0, binarySearch(a, 2));
		Assert.assertEquals(1, binarySearch(a, 3));
		Assert.assertEquals(2, binarySearch(a, 5));
		Assert.assertEquals(3, binarySearch(a, 7));
		Assert.assertEquals(4, binarySearch(a, 9));
		Assert.assertEquals(5, binarySearch(a, 11));
		Assert.assertEquals(6, binarySearch(a, 13));
		Assert.assertEquals(7, binarySearch(a, 15));
		Assert.assertEquals(8, binarySearch(a, 17));
		Assert.assertEquals(-1, binarySearch(a, 1));
	}

}
